package set;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Combinations77 {
    @Test
    public void testSubsetsRecursively() {
        combinationsRecursively(4, 3);
        combinationsRecursively(5, 3);
    }

    public List<List<Integer>> combinationsRecursively(int n, int k) {
        List<List<Integer>> result = new ArrayList<>(2 << n);
        doCombinationsRecursively1(n, k, 1, new LinkedList<>(), result);
        print(n, k, result);
        return result;
    }

    public void doCombinationsRecursively1(int n, int k, int current, LinkedList<Integer> combine, List<List<Integer>> result) {
        if (combine.size() == k) {
            result.add(new ArrayList<>(combine));
            return;
        }

        if (current > n || combine.size() + n - current + 1 < k) {
            return;
        }
        combine.addLast(current);
        doCombinationsRecursively1(n, k, current+1, combine, result);
        combine.removeLast();
        doCombinationsRecursively1(n, k, current+1, combine, result);
    }

    public void print(int n, int k, List<List<Integer>> result) {
        System.out.println("--------------------------");
        System.out.format("n: %d, k: %d, result.size: %d\n", n, k, result.size());
        for (List<Integer> subset: result) {
            System.out.println(subset);
        }
        System.out.println();
    }
}
